个点 条边的无向无环图，其实就是一个森林。
题目要求最小化两个量：灯数和只被一边照亮的边数。
一个做法是定义两个 数组，分别表示最小灯数和在灯数最小情况下的一边被照亮的最小边数。
然后你发现它们是一起转移的，那么就有一个极妙的做法：
将它们的贡献算在一起，因为灯数的优先级高，所以给它乘上一个权值 。（这里 可以取任意不小于 的值 ，可以理解为 进制的高低位），那么加一个灯贡献加 ，加一条单灯边贡献加 ，
那么转移就变为：
最后只需要除以 ，和膜 便能得到分别的答案。
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 1000 , k = 1005;
int T , n , m;
vector< int > Graph[ MAXN + 5 ];
int dp[ 2 ][ MAXN + 5 ];
void dfs( int u , int fa ) {
dp[ 0 ][ u ] = 0 , dp[ 1 ][ u ] = k;
for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
int v = Graph[ u ][ i ];
if( v == fa ) continue;
dfs( v , u );
dp[ 0 ][ u ] += dp[ 1 ][ v ] + 1;
dp[ 1 ][ u ] += min( dp[ 0 ][ v ] + 1 , dp[ 1 ][ v ] );
}
}
int main( ) {
scanf("%d",&T);
while( T -- ) {
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= n ; i ++ ) Graph[ i ].clear() , dp[ 0 ][ i ] = 0 , dp[ 1 ][ i ] = 0;
for( int i = 1 , u , v ; i <= m ; i ++ ) {
scanf("%d %d",&u,&v); u ++ , v ++;
Graph[ u ].push_back( v );
Graph[ v ].push_back( u );
}
int Ans1 = 0 , Ans2 = 0;
for( int i = 1 ; i <= n ; i ++ )
if( !dp[ 1 ][ i ] ) {
dfs( i , 0 );
Ans1 += min( dp[ 0 ][ i ] , dp[ 1 ][ i ] ) / k;
Ans2 += min( dp[ 0 ][ i ] , dp[ 1 ][ i ] ) % k;
}
printf("%d %d %d\n", Ans1 , m - Ans2 , Ans2 );
}
return 0;
}